rekursive Funktion

rekursive Funktion,

 

in der Mathematik eine mittels rekursiver Definition gewonnene Funktion, für die es ein Berechnungsverfahren der Funktionswerte gibt. Als primitiv-rekursiv (K. Gödel, 1931) bezeichnet man:

 

a) die Zahl 0; die Funktion f (x₁, x₂,. .., x_n) = 0;

 

b) die Identitäts- oder Projektionsfunktionen

 

f (x₁, x₂,. .., x_n) = x_ν, 1 ≦ ν ≦ n;

 

c) die Nachfolgerfunktion N (x) = x' (= x + 1).

 

Der Begriff der primitiv-rekursiven Funktion erfasst aber nicht alle im anschaulichen Sinne berechenbaren Funktionen (z. B. die ackermannsche Funktion von F. W. Ackermann, 1928). Er wurde deshalb 1934 von Gödel zur allgemein-rekursiven Funktion erweitert: Allgemein-rekursiv nennt man Funktionen, die durch Gleichungen zwischen Termen und definierten Hilfsfunktionen so festgelegt werden, dass es zu jedem r-Tupel von Zahlen n₁, n₂,. .., n_r genau eine Zahl n gibt, sodass eine Funktion ϕ (n₁, n₂,. .., n_r) = n durch endlich viele Anwendungen der folgenden Schritte zu erhalten ist: 1) Einsetzen von Zahlen für Variable; 2) Übergang von einem Ausdruck a und von einem Ausdruck der Form b = c zu jenem Ausdruck, der aus a dadurch entsteht, dass man an einer oder mehreren Stellen b durch c ersetzt.

 

Ein Lehrsatz der Rekursionstheorie besagt, dass die Menge der so definierten rekursiven Funktion und die Mengen der mit Register- beziehungsweise Turing-Maschinen erzeugbaren Funktionen identisch sind. (churchsche Hypothese)